import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class ThreeSort {
    public  int[] bubbleSort(int[] arr) {
        int[] array = Arrays.copyOf(arr,arr.length);
        for(int i = 1;i < array.length ; i ++) {
            Boolean a = true;
            for(int j = 0; j < array.length - i; j++) {
                if(array[j] > array[j + 1]) {
                    swap(array,j,j+1);
                    a = false;
                }
            }
            if(a) {
                return array;
            }
        }
        return array;
    }
    //快速排序递归实现
    public int[] quickSortPlus(int[] array) {
        int[] arr = Arrays.copyOf(array,array.length);
        Deque<Integer> stack = new LinkedList<>();
        int left = 0;
        int right = array.length-1;
        int pivot = 0;
        stack.push(left);
        stack.push(right);
        while (!stack.isEmpty()) {
            right= stack.pop();
            left = stack.pop();
            pivot = partition1(arr,left,right);
            if(pivot > left+1) {
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot < right-1) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }
        return arr;
    }
    public int[] quickSort(int[] array) {
        int[] arr = Arrays.copyOf(array,array.length);
        int left = 0;
        int right = arr.length - 1;
        quick(arr,left,right);
        return arr;
    }
    private void quick(int[] array,int begin,int end) {
        if(begin >= end) {
            return;
        }
        if(end - begin < 20) {
            //插入排序
            //......
            return;
        }
        int centre = partition1(array,begin,end);
        //int centre = partition2(array,begin,end);
        //int centre = partition3(array,begin,end);
        quick(array,centre + 1,end);
        quick(array,begin,centre - 1);
    }
    //挖坑法
    private  int partition1(int[] array,int left,int right) {
        int tmp = array[left];
        while (left < right) {
            while (left< right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            while (left< right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }
    //Hoare版
    private  int partition2(int[] array,int left,int right) {
        int tmp = midThree(array,left,right);
        int i = left;
        while (left < right) {
            while (left< right && array[right] >= tmp) {
                right--;
            }
            while (left< right && array[left] <= tmp) {
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,i);
        return left;
    }
    //前后指针法
    private int partition3(int[] array,int left,int right) {
        int prev = left ;
        int cur = left+1;
        while (cur <= right) {
            if(array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }
    private  int midThree(int[] array,int left,int right) {
        int mid = (left + right) / 2;
        //6  8
        if (array[left] < array[right]) {
            if (array[mid] < array[left]) {
                return left;
            } else if (array[mid] > array[right]) {
                return right;
            } else {
                return mid;
            }
        } else {
            //array[left] > array[right]
            if (array[mid] < array[right]) {
                return right;
            } else if (array[mid] > array[left]) {
                return left;
            } else {
                return mid;
            }
        }
    }
    private void swap (int[] arr,int m,int n) {
        int tmp = arr[m];
        arr[m] = arr[n];
        arr[n] = tmp;
    }
    public  void mergeSort1(int[] array) {
        mergeSortFunc(array,0,array.length-1);
    }
    private  void mergeSortFunc(int[] array,int left,int right) {
        if(left >= right) {
            return;
        }

        int mid = (left+right) / 2;
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        merge(array,left,right,mid);
    }

    private  void merge(int[] array,int start,int end,int mid) {
        int s1 = start;
        //int e1 = mid;
        int s2 = mid+1;
        //int e2 = end;
        int[] tmp = new int[end-start+1];
        int k = 0;//tmp数组的下标
        while (s1 <= mid && s2 <= end) {
            if(array[s1] <= array[s2]) {
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }
        while (s1 <= mid) {
            tmp[k++] = array[s1++];
        }
        while (s2 <= end) {
            tmp[k++] = array[s2++];
        }

        for (int i = 0; i < tmp.length; i++) {
            array[i+start] = tmp[i];
        }

    }
}
